/*
 * PatternTreeModel.java
 *
 * Created on 08 January 2005, 17:14
 */

package org.datamining.guha.model;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.datamining.guha.model.literal.Literal;
import org.datamining.guha.model.node.Node;
import org.datamining.guha.model.node.NodeFactory;
import org.datamining.guha.model.node.iterative.IterativeNodeFactory;
import org.datamining.guha.utils.RootNodePool;

/**
 * PatternTree consists of:
 * 
 * <ol>
 * <li> <code>root</code> Node which has null Literal and all its successors
 * represents indiviual PatternTrees. </li>
 * <li> <code>FrequencyOrderedList</code> which contains all Literals from
 * model along with their frequencies. </li>
 * <li> <code>literalNodeList</code> contains references to end (or beginning
 * if you like) of thread which connectes Nodes with the same Literal in whole
 * model. Go through thread and count frequencies and you get frequency of
 * specific Literal in whole model. </li>
 * </ol>
 * 
 * @author Lukas Vlcek
 */
public class PatternTreeModel {

	private static Log log = LogFactory.getLog(PatternTreeModel.class);

	private NodeFactory nodeFactory;

	private FrequencyOrderedList frList;

	private Node modelRoot;

	private List<LiteralNodeListItem> literalNodeList;

	private RootNodePool rootNodePool;

	/* Buffer for source rows. */
	private LiteralSourceRow[] rowBuffer;

	private int bufferUsed;

	/**
	 * Creates a new instance of PatternTreeModel.
	 * 
	 * @param modelLiteralsCount
	 *            Number of distinct {@link Literal}s in the model.
	 * @param rowBufferSize
	 * @param nodeProvider
	 *            Implementation of {@link NodeFactory} which is used as a
	 *            provider of (@link Node}s for the model structures.
	 */
	public PatternTreeModel(int modelLiteralsCount, int rowBufferSize,
			NodeFactory nodeProvider) {

		// (note that we need to count 2 positions for each Literal [A, negA])
		this.frList = new FrequencyOrderedList(modelLiteralsCount * 2);

		this.nodeFactory = nodeProvider;
		// root is a Node without Literal and next/previousLiteralNode.
		this.modelRoot = nodeProvider.getNode(null, null, null, 1);

		this.literalNodeList = new ArrayList<LiteralNodeListItem>(
				modelLiteralsCount * 2);

		RootNodePool pool = new RootNodePool(modelLiteralsCount * 2,
				IterativeNodeFactory.getInstance());
		this.rootNodePool = pool;
		// initialize buffer for source rows.
		this.rowBuffer = new LiteralSourceRow[rowBufferSize];
		this.bufferUsed = 0;
	}

	/** @return FrequencyOrderedList from this model. */
	public FrequencyOrderedList getFrList() {
		return this.frList;
	}

	/** @return Node which is root of the whole model. */
	public Node getModelRoot() {
		return this.modelRoot;
	}

	/**
	 * Insert given {@link LiteralSourceRow} to the model. It also means that
	 * FrequencyOrderedList is updated as well prior to adding this row to the
	 * model.
	 * 
	 * @param row
	 */
	public void parseSourceRow(LiteralSourceRow row) {

		log.debug("adding new row: " + row);
		// update frList first and then update root.*
		frList.update(row);
		log.debug("frList: " + frList);

		if (bufferUsed < rowBuffer.length) {
			addRowIntoBuffer(row);
		} else {
			flushBuffer();
			addRowIntoBuffer(row);
		}

	}

	/** How many source rows are waiting in buffer. */
	public int getBufferUsed() {
		return this.bufferUsed;
	}

	/**
	 * Add all source rows from buffer into model and empty buffer.
	 * TODO Clean the rowBuffer better (by one operation in the end!)
	 */
	public void flushBuffer() {

		rearrangePatternTree(modelRoot, frList);

		for (int i = 0; i < rowBuffer.length; i++) {
			if (rowBuffer[i] != null) {
				rowBuffer[i].setNodeFactory(nodeFactory);
				updatePatternTree(rowBuffer[i]);
				rowBuffer[i] = null;
			}
		}
		bufferUsed = 0;
	}

	/** Store row in buffer and increment bufferUsed counter. */
	private void addRowIntoBuffer(LiteralSourceRow row) {
		rowBuffer[bufferUsed] = row;
		bufferUsed++;
	}

	/**
	 * After FrequencyOrderedList has been updated we must perform update of the
	 * root.* tree.
	 * 
	 * @param row input data to be added into model.
	 */
	private void updatePatternTree(LiteralSourceRow row) {

		/* Convert row into tree so that it can be added into model. */
		Node tree = row.getTreeOrderedAccordingTo(frList);

		/* Rearrange whole root.* according to rfrList. */
		// rearrangePatternTree(Root, frList);
		/* Now when thole model is rearranged we can safely add new tree */
		addToPatternTree(modelRoot, tree, literalNodeList);
	}

	/**
	 * <p>
	 * We assume that frList was updated and thus we need to rearrange
	 * everything after Root (or first Node argument).
	 * <p>
	 * In fact this method is called recursively. Its function is: Rearrange all
	 * subtrees following given "Root" Node according to given
	 * FrequencyOrderedList. This means that FrequencyOrderedList must be
	 * shorter by one Node. This is beacuse we assume given Node to be a Root
	 * which don't need to be modified.
	 * </p>
	 */
	private void rearrangePatternTree(Node node,
			FrequencyOrderedList frLocalList) {

		// This situation shouldn't occur.
		// Consider firing an exception.
		/*
		 * if (node.getLiteral() == null && node.getSuccessors().size() == 0) {
		 * return; }
		 */

		// If node has no child then return.
		if (node.getSuccessors().isEmpty()) {
			if (log.isDebugEnabled()) {
				log.debug("Found node without childs: " + node
						+ " (likely end of branch)");
			}
			return;
		}

		// @todo insufficient .sort() call !!! and creation of new List object.
		List<Literal> frL = frLocalList.getLiteralList();
		// log.debug(frLocalList.toString());
		// If we have any Literals in frList then get first one else return;
		Literal litFr = null;
		if (frL.size() > 0) {
			// @todo zbytecne pretypovani
			litFr = frL.get(0);
		} else {
			return;
		}

		// for every successor do...
		List<Node> suc = node.getSuccessors();
		// for (Node child: suc) { // generates ConcurrentModificationException
		// !!!
		for (int i = 0; i < suc.size(); i++) {
			/*
			 * We create frShorterLocalList now as it can be used multiple times
			 * in the following code.
			 */
			// @todo Creating new Objects!!
			FrequencyOrderedList frShorterLocalList = frLocalList
					.getChildFrequencyList();

			Node child = suc.get(i);

			// if its Literal != litFr taken from frList then...
			if (!child.getLiteral().equals(litFr)) {

				List<Node> subchilds = child.getNodesWithLiteral(litFr);
				if (subchilds != null) {
					int ch = subchilds.size();

					while (--ch >= 0) {
						Node subchild = subchilds.get(ch);
						propagateNodeUp(child, subchild);
					}
				}

				/*
				 * // until subtree contains any Node(s) with litFr then... Node
				 * subchild = child.getNodeWithLiteral(litFr); while (subchild !=
				 * null) { // propagate that Node(s) up. propagateNodeUp(child,
				 * subchild);
				 * 
				 * subchild = child.getNodeWithLiteral(litFr); }
				 */

				/*
				 * Temprary root Node is used which allows correct call to
				 * rearrangePatternTree() method.
				 */
				Node tmpRoot = rootNodePool.getTempRoot();
				tmpRoot.getSuccessors().add(child);
				rearrangePatternTree(tmpRoot, frShorterLocalList);
				rootNodePool.returnTempNode(tmpRoot);

			} else {

				// take subtree and rearrange accoring to "frList - 1"
				rearrangePatternTree(child, frShorterLocalList);

			}
		}

	}

	/**
	 * Move Node child up until Node top is direct parent of Node child.
	 */
	private void propagateNodeUp(Node top, Node child) {

		/* until parent of child is not top node then... */
		while (!child.getParent().equals(top)) {
			moveUp(child);
		}
		/* now move child up */
		moveUp(child);
	}

	/**
	 * Move given node one position "up"
	 */
	private void moveUp(Node n) {

		if (n.getParent().isRoot())
			return;

		Node p = n.getParent();

		if (p.getFrequency() == n.getFrequency()) {

			LinkedList<Node> tmpList = n.getSuccessors();
			int i = p.getParent().getSuccessors().indexOf(p);
			p.getParent().setSuccessor(i, n);
			n.setParent(p.getParent());
			n.setSuccessors(p.getSuccessors());
			n.setSuccessor(0, p);
			p.setParent(n);
			p.setSuccessors(tmpList);
			if (!p.getSuccessors().isEmpty()) {
				for (int s = p.getSuccessors().size(); s > 0; s--) {
					Node suc = p.getSuccessor(s - 1);
					suc.setParent(p);
				}
			}
		}

		if (p.getFrequency() > n.getFrequency()) {
			// #1
			Node p2 = nodeFactory.getNode(p.getLiteral(), null, null, p
					.getFrequency());
			// set next/previousLiteralNode
			p2.setNextLiteralNode(p.getNextLiteralNode());
			p2.setPreviousLiteralNode(p);
			p.setNextLiteralNode(p2);
			if (p2.getNextLiteralNode() != null) {
				Node tmp = p2.getNextLiteralNode();
				tmp.setPreviousLiteralNode(p2);
			}

			p2.setParent(p.getParent());
			p.getParent().addSuccessor(p2);

			// #2
			p2.setFrequency(n.getFrequency());
			// #3
			long fr = p.getFrequency() - p2.getFrequency();
			p.setFrequency(fr);
			// #4
			p2.addSuccessor(n);
			n.setParent(p2);
			// #5
			List<Node> list = p.getSuccessors();
			// @todo Find better solution
			int position = -1;
			for (int s = list.size(); s > 0; s--) {
				Node suc = list.get(s - 1);
				if (suc == n) {
					position = s - 1;
				}
			}
			if (position >= 0) {
				list.remove(position);
			}
			// #6
			moveUp(n);
		}
	}

	/**
	 * We must find the best place where new row can be added. That means
	 * traversing whole root.* to find the best place. We assume that row is
	 * ordered according to FrequencyOrderedList.
	 */
	private void addToPatternTree(Node root, Node row,
			List<LiteralNodeListItem> literalNodeList) {

		// At the beginning there is no treeroot.
		if (root.getSuccessors().size() == 0) {
			root.addSuccessor(row);
			row.setParent(root);
			inicializeLiteralNodeList(literalNodeList, row);
			return;
		}

		int depth = 0;
		Node maxFittingNode = null;
		// traverse all successors of root
		List<Node> suc = root.getSuccessors();
		for (int i = suc.size(); i > 0; i--) {
			Node child = suc.get(i - 1);
			// find best fitness of given branch
			Node fittingNode = findMaxFitness(child, row);

			if (fittingNode != null) {
				if (maxFittingNode == null) {
					maxFittingNode = fittingNode;
				}
				// if this fitness is better then the
				// previous one then remember it.
				int tempDepth = fittingNode.getDepth();
				if (tempDepth > depth) {
					depth = tempDepth;
					maxFittingNode = fittingNode;
				}
			}
		}

		// If no fittness found then store given tree
		// as a new branch of root.
		if (maxFittingNode == null) {
			root.getSuccessors().add(row);
			updateLiteralNodeList(literalNodeList, row);
			row.setParent(root);
		}
		// else ...
		else {
			// TODO Manage increase factor according to tree...
			// TODO add root parameter to increaseUpToRoot() method !!!
			// Node appendAfterNode =
			// row.getNodeWithLiteral(maxFittingNode.getLiteral());
			List<Node> list = row.getNodesWithLiteral(maxFittingNode
					.getLiteral());
			Node appendAfterNode = list.get(0);

			// maxFittingNode.increaseUpToRoot(1); // NO !!!!
			// there was a bug!!! not increase by 1 but get real frequency.
			// maxFittingNode.increaseFrequencyUpToRoot(appendAfterNode.getLiteral().getFrequency());
			maxFittingNode.increaseFrequencyUpToRoot(appendAfterNode
					.getFrequency());

			// if there are any children left then...
			if (!appendAfterNode.getSuccessors().isEmpty()) {
				Node appendFromNode = appendAfterNode.getSuccessor(0);
				maxFittingNode.getSuccessors().add(appendFromNode);
				updateLiteralNodeList(literalNodeList, appendFromNode);
				appendFromNode.setParent(maxFittingNode);
			}
			// TODO What is happening to all Node from row to appendAfterNode ?
			// We could push them in some sort of NodePool. And we need to
			// "clear"/"reset" them also (so that all references are nulled.
		}
	}

	/**
	 * Finds ... what? TODO This method should be in Node class.
	 */
	private Node findMaxFitness(Node branch, Node row) {

		if (branch.getLiteral() != row.getLiteral()) {
			return null;
		}

		Node nodeToReturn = branch;
		// start of iterative algorithm
		int maxDepth = 1;
		int actualDepth = 1;

		Node rowPointer = null;
		if (!row.getSuccessors().isEmpty()) {
			rowPointer = (Node) row.getSuccessors().getFirst();
		} else {
			// we have reached end of row
			return nodeToReturn;
		}

		Node n = branch;
		Node succ = n.getLastSuccessor();
		if (succ != null) {
			actualDepth++;
		}

		// while there are any successors
		while (succ != null) {

			boolean canGoDown = false;

			// checkLiteral
			if (succ.getLiteral() == rowPointer.getLiteral()) {
				if (actualDepth > maxDepth) {
					nodeToReturn = succ;
					maxDepth = actualDepth;
					// System.out.println("Max deep " + nodeToReturn);
					canGoDown = true;
				}
			}

			// get next successor

			Node x = null;
			if (canGoDown) {
				// traverse down
				x = succ.getLastSuccessor();
				if (x != null) {
					actualDepth++;
					if (!rowPointer.getSuccessors().isEmpty()) {
						rowPointer = (Node) rowPointer.getSuccessor(0);
					} else {
						succ = null;
						continue;
					}
					succ = x;
					continue;
				}
			}

			// get neighbour
			x = succ.getParent().getPreviousSuccessor();
			if (x != null) {
				succ = x;
				continue;
			}

			// traverse up until new Node is found or exit
			while (x == null) {
				x = succ.getParent();
				if (x != branch) {
					actualDepth--;
					rowPointer = rowPointer.getParent();
					succ = x.getParent().getPreviousSuccessor();
					if (succ != null) {
						break;
					}
					if (succ == null) {
						succ = x;
						x = null;
					}
				} else {
					succ = null;
					break;
				}
			}
		}

		return nodeToReturn;
		// end of iterative algorithm
		/*
		 * Node rowShorter = null; if (row.getSuccessors().size() > 0) {
		 * rowShorter = row.getSuccessor(0); } else { return nodeToReturn; // we
		 * have reached end of branch. }
		 * 
		 * int depth = 0; List suc = branch.getSuccessors(); for (int i =
		 * suc.size(); i > 0 ; i--) { Node child = (Node) suc.get(i-1); Node
		 * tempFitness = findMaxFitness(child, rowShorter); if (tempFitness !=
		 * null) { int tempDepth = tempFitness.getDepth(); // @todo if tempDepth ==
		 * delce row then return. Uz nema cenu hledat dal. if (tempDepth >
		 * depth) { depth = tempDepth; nodeToReturn = tempFitness; } } }
		 * 
		 * 
		 * return nodeToReturn;
		 */
	}

	/**
	 * <p>
	 * Rebuilds whole modelRoot.* according to FrequencyOrderedList. This method
	 * should result into more compressed form of the tree. If
	 * FrequencyOrderedList significantly changes after some new
	 * LiteralSourceRow(s) are added into model then there is a risk that tree
	 * is too expanded.
	 * </p>
	 * <p>
	 * This method builds a new Root with fully packed tree.
	 * </p>
	 */
	public void rebuildPatternTree() {

		List lastNodes = modelRoot.getLastChilds();

		/*
		 * List lastNodes = new ArrayList();
		 * 
		 * List suc = Root.getSuccessors(); for (int i = suc.size(); i > 0 ;
		 * i--) { Node child = (Node) suc.get(i-1);
		 * lastNodes.addAll(child.getLastChilds()); }
		 */

		/*
		 * @todo Consider if we need to propagateNodeUp() whether it is better
		 * to just pull out one thread without propagating its last Node
		 * upwards.
		 * 
		 * One of reasons can be that if we propagateNodeUp() then this thread
		 * is not ordered according to FrequencyOrderedList and we have to
		 * reorder it first.
		 */
		Node newRoot = nodeFactory.getNode(null, null, null, 1);
		List<LiteralNodeListItem> newLiteralNodeList = new ArrayList<LiteralNodeListItem>();

		for (int i = lastNodes.size(); i > 0; i--) {
			Node node = (Node) lastNodes.get(i - 1);
			propagateNodeUp(modelRoot, node);

			Node tmpRoot = rootNodePool.getTempRoot();
			tmpRoot.getSuccessors().add(node);
			node.setParent(tmpRoot);
			rearrangePatternTree(tmpRoot, frList);

			Node newRow = tmpRoot.getSuccessor(0);
			resetLiteralNodes(newRow);
			addToPatternTree(newRoot, newRow, newLiteralNodeList);
			rootNodePool.returnTempNode(tmpRoot);

		}

		modelRoot = newRoot;
		literalNodeList = newLiteralNodeList;

	}

	/**
	 * At the beginning the literalNodeList is empty. We can use the first input
	 * data row to initialize it.
	 * 
	 * @param row
	 *            is a root Node of given tree. In this case we assume that it
	 *            is just linear tree (no branching).
	 */
	private void inicializeLiteralNodeList(
			List<LiteralNodeListItem> literalNodeList, Node row) {
		Node n = row;
		Literal l = row.getLiteral();
		LiteralNodeListItem listItem = new LiteralNodeListItem(l, n);
		literalNodeList.add(listItem);
		if (!row.getSuccessors().isEmpty()) {
			n = row.getSuccessor(0);
			inicializeLiteralNodeList(literalNodeList, n);
		}
	}

	/**
	 * ...
	 * 
	 * @param row
	 *            is a root Node of given tree. In this case we assume that it
	 *            is just linear tree (no branching).
	 */
	private void updateLiteralNodeList(
			List<LiteralNodeListItem> literalNodeList, Node row) {
		Node n = row;
		boolean found = false;

		for (int i = literalNodeList.size(); (i > 0 && found == false); i--) {
			LiteralNodeListItem listItem = (LiteralNodeListItem) literalNodeList
					.get(i - 1);
			// if literalNodeList already contains tree.literal then...
			if (listItem.getLiteral().equals(n.getLiteral())) {
				Node tmp = listItem.getNodeReference();
				// update listItem.setNodeReference
				listItem.setNodeReference(n);
				n.setPreviousLiteralNode(null);
				n.setNextLiteralNode(tmp);
				tmp.setPreviousLiteralNode(n);
				found = true;
			}
		}
		// else add it.
		if (found == false) {
			Literal l = row.getLiteral();
			LiteralNodeListItem newListItem = new LiteralNodeListItem(l, n);
			literalNodeList.add(newListItem);
		}
		if (!row.getSuccessors().isEmpty()) {
			n = row.getSuccessor(0);
			updateLiteralNodeList(literalNodeList, n);
		}
	}

	/**
	 * Reset next/previousLiteralNode to null for all Nodes in given tree.
	 * 
	 * @param row
	 *            is a root Node of given tree. In this case we assume that it
	 *            is just linear tree (no branching).
	 */
	private void resetLiteralNodes(Node row) {
		row.setNextLiteralNode(null);
		row.setPreviousLiteralNode(null);
		if (!row.getSuccessors().isEmpty()) {
			Node n = row.getSuccessor(0);
			resetLiteralNodes(n);
		}
	}

	/**
	 * @return Node reference to the 'first' node of branch which conatins given
	 *         Literal.
	 */
	private Node getBranchWithLiteral(Literal literal) {
		Node node = null;

		for (int i = literalNodeList.size(); i > 0; i--) {
			LiteralNodeListItem item = (LiteralNodeListItem) literalNodeList
					.get(i - 1);
			if (item.getLiteral().equals(literal)) {
				return item.getNodeReference();
			}
		}
		return node;
	}

	/**
	 * ...
	 */
	public String toStringLiteralNodeList() {
		StringBuffer sb = new StringBuffer();
		sb.append("literalNodeList: " + literalNodeList.size() + "\n");

		for (int i = 0; i < literalNodeList.size(); i++) {
			LiteralNodeListItem item = (LiteralNodeListItem) literalNodeList
					.get(i);
			sb.append(item.getLiteral() + " : ");
			Node n = item.getNodeReference();
			while (n != null) {
				sb.append(n + " ");
				if (n.getNextLiteralNode() != null) {
					n = n.getNextLiteralNode();
				} else {
					n = null;
				}
			}
			sb.append("\n");
		}
		return sb.toString();
	}

	/** @return long support of given Literal in the model. */
	public long getLiteralSupport(Literal literal) {
		return this.frList.getLiteralSupport(literal);
	}

	/**
	 * @return long support of given pattern. Pattern is specified as a List of
	 *         Literals. TODO Check that given List doesn't contain duplicities.
	 */
	public long getPatternSupport(List<Literal> pattern) {

		// Convert pattern to tree ordered according to frList
		// TODO It is not necessary to create tree
		LiteralSourceRow tmpRow = new LiteralSourceRowImpl(pattern);
		tmpRow.setNodeFactory(nodeFactory);
		
		Node tmpNode = tmpRow.getTreeOrderedAccordingTo(this.frList);
		Node conversed = nodeFactory.getNode(tmpNode.getLiteral(), null, null, 1);

		while (!tmpNode.getSuccessors().isEmpty()) {
			tmpNode = tmpNode.getSuccessor(0);
			Node parent = nodeFactory.getNode(tmpNode.getLiteral(), null,
					null, 1);
			conversed.setParent(parent);
			parent.addSuccessor(conversed);
			conversed = conversed.getParent();
		}

		return getTreeSupport(conversed);
	}

	/**
	 * @return long support of given tree. This tree is ordered conversely to
	 *         frList.
	 * 
	 * TODO Given tree is linear and in the future this should be changed. The
	 * method will accept List<Literal> instead.
	 */
	private long getTreeSupport(Node tree) {
		long support = 0;

		Literal literal = tree.getLiteral();
		// if tree is represented only by one Node then
		// return support of its Literal.
		if (tree.getSuccessors().isEmpty()) {
			return getLiteralSupport(literal);
		}

		// Make tree shorter by first Node.
		tree = tree.getSuccessor(0);

		Node literalBranch = getBranchWithLiteral(literal);
		while (literalBranch != null) {
			// if there is pattern up to Root
			// then get support of node with 'last' Literal
			if (literalBranch.containsPatterUpToRoot(tree)) {
				support += literalBranch.getFrequency();
			}
			literalBranch = literalBranch.getNextLiteralNode();
		}

		return support;
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();

		sb.append("Freq: ");
		sb.append(this.frList + "\n");
		sb.append(this.modelRoot);
		sb.append(toStringLiteralNodeList() + "\n");

		return sb.toString();
	}

	public void setNodeFactory(NodeFactory nodeProvider) {
		this.nodeFactory = nodeProvider;
	}

	public NodeFactory getNodeFactory() {
		return nodeFactory;
	}

}
